package problem.year2023.month05

import kotlin.math.pow


/**
 * @author LiangMu
 * @version $Id: Day02.java, v 0.1 2023年05月02日 14:34 LiangMu Exp $$
 */
object Day02 {

    /**
     * 给定三个整数 x 、 y 和 bound ，返回 值小于或等于 bound 的所有 强整数 组成的列表 。
     *
     * 如果某一整数可以表示为 xi + yj ，其中整数 i >= 0 且 j >= 0，那么我们认为该整数是一个 强整数 。
     *
     * 你可以按 任何顺序 返回答案。在你的回答中，每个值 最多 出现一次。
     *
     * 示例1：
     * 输入：x = 2, y = 3, bound = 10
     * 输出：[2,3,4,5,7,9,10]
     * 解释：
     * 2 = 20 + 30
     * 3 = 21 + 30
     * 4 = 20 + 31
     * 5 = 21 + 31
     * 7 = 22 + 31
     * 9 = 23 + 30
     * 10 = 20 + 32
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/powerful-integers
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    fun powerfulIntegers(x: Int, y: Int, bound: Int): List<Int> {
        if (x == 1 || y == 1) {
            val z = if (x == 1) y.toDouble() else x.toDouble()
            var px = 0.0
            val res = ArrayList<Int>()
            while (1 + z.pow(px) <= bound) {
                res.add(1 + z.pow(px).toInt())
                ++px
            }
            return res.sorted()
        } else {
            // 以 x 为底，做 y 向遍历
            val res1 = common(x, bound, y)
            val res2 = common(y, bound, x)
            res1.addAll(res2)
            return ArrayList(res1).sorted()
        }
    }

    private fun common(
        x: Int,
        bound: Int,
        y: Int
    ): MutableSet<Int> {
        val set = HashSet<Int>()
        var px = 0.0
        while (x.toDouble().pow(px) <= bound) {
            do {
                var yp = 0.0
                var num = x.toDouble().pow(px) + y.toDouble().pow(yp)
                while (num <= bound) {
                    set.add(num.toInt())
                    ++yp
                    num = x.toDouble().pow(px) + y.toDouble().pow(yp)
                }
                ++px
            } while (num <= bound)
        }
        return set
    }
}

fun main() {
    val powerfulIntegers = Day02.powerfulIntegers(2, 1, 10)
    println(powerfulIntegers.joinToString(",", "[", "]"))
}
